package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0052.java
 * @Author : WangRuoyu
 * @Date 2023/11/3 21:52
 */


public class Q0052 {
    int len;
    int[][] st;
    boolean[][] tmp;
    int res = 0;
    int[] dx = {1, 1, 0, -1, -1, -1, 0, 1};
    int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};

    private void addSt(int x, int y, int c) {
        st[x][y] += c;
        for (int i = 0; i < 8; i++) {
            int p = x + dx[i];
            int q = y + dy[i];
            while (p >= 0 && p < len && q >= 0 && q < len) {
                st[p][q] += c;
                p += dx[i];
                q += dy[i];
            }
        }
    }

    private void dfs(int k) {
        if (k == len) {
            res++;
            return;
        }
        for (int i = 0; i < len; i++) {
            if (st[k][i] == 0) {
                addSt(k, i, 1);
                tmp[k][i] = true;
                dfs(k + 1);
                tmp[k][i] = false;
                addSt(k, i, -1);
            }
        }
    }

    public int totalNQueens(int n) {
        this.len = n;
        this.tmp = new boolean[n][n];
        this.st = new int[n][n];
        dfs(0);
        return res;
    }

    public static void main(String[] args) {
        Q0052 sl = new Q0052();
        int n = 4;
        System.out.println(sl.totalNQueens(n));
    }
}